home *** CD-ROM | disk | FTP | other *** search
/ SPACE 1 / SPACE - Library 1 - Volume 1.iso / program / 441 / dlibs12 / malloc.c < prev    next >
C/C++ Source or Header  |  1990-11-23  |  4KB  |  178 lines
  1. #include <osbind.h>
  2. #include <stddef.h>
  3. #include <malloc.h>
  4.  
  5. #define    MAXBLK        16
  6. #define    FREE        0x00
  7. #define    USED        0x80
  8. #define    NULLBLK        0x80000000L
  9.  
  10. char    *_mblk[MAXBLK] =        /* system memory heaps */
  11.     {
  12.     NULL, NULL, NULL, NULL,
  13.     NULL, NULL, NULL, NULL,
  14.     NULL, NULL, NULL, NULL,
  15.     NULL, NULL, NULL, NULL
  16.     };
  17.  
  18. long    _msiz[MAXBLK] =            /* allocated heap sizes */
  19.     {
  20.     0L, 0L, 0L, 0L,
  21.     0L, 0L, 0L, 0L,
  22.     0L, 0L, 0L, 0L,
  23.     0L, 0L, 0L, 0L
  24.     };
  25.  
  26. /*
  27.  *    Up to 16 heaps are allocated from the operating system as they are
  28.  *    needed to fill requests for dynamic memory.  These heaps are them
  29.  *    divided into blocks for parcelling out by the user-callable memory
  30.  *    allocation routines.  If all the storage in a heap is freed, the heap
  31.  *    will be freed to the OS.  Each heap beings with a pointer to the first
  32.  *    free block, or NULL if there are no free blocks in this heap.  Each
  33.  *    block begins with a 4-byte header which defines the number of bytes
  34.  *    in the block, including the header.  Since blocks in a heap are known
  35.  *    to be contiguous, this value also defines the beginning of the next
  36.  *    block in the heap.  The high bit of the header is set if the block
  37.  *    is used and clear if it is free.  The heaps ends with a block header
  38.  *    which indicates a used block containing 0 bytes.  The is the constant
  39.  *    value NULLBLK.  Free blocks contain an additional pointer field,
  40.  *    immediatly following the header, which is a pointer to the header of
  41.  *    the next free block, or NULL.
  42.  */
  43.  
  44. static char *makeblk(size)
  45.     long size;
  46. /*
  47.  *    Get a new major block from the system that will hold at least
  48.  *    <size> bytes.
  49.  */
  50.     {
  51.     register int i;
  52.     register char *p;
  53.     register long n, minsiz, bsiz, *q;
  54.  
  55.     minsiz = (size + 0x200L) & ~0x1FFL;    /* round up to nearest 512 */
  56.     if(minsiz < _BLKSIZ)
  57.         bsiz = _BLKSIZ;
  58.     else
  59.         bsiz = minsiz;
  60.     for(i=0; i<MAXBLK; ++i)
  61.         {
  62.         if(_mblk[i] != NULL)
  63.             continue;        /* skip used heaps */
  64.         n = Malloc(-1L);
  65.         n = ~0x1FFL & (n - 512L);    /* system memory available */
  66.         if(n < bsiz)
  67.             {
  68.             if(n < minsiz)
  69.                 return(NULL);
  70.             else
  71.                 bsiz = minsiz;
  72.             }
  73.         _mblk[i] = p = ((char *) Malloc(bsiz));
  74.         _msiz[i] = bsiz;
  75.         q = ((long *) (p + bsiz));    /* thread starting blocks */
  76.         q[-1] = NULLBLK;
  77.         q = ((long *) (p + 4L));
  78.         q[-1] = (long) q;
  79.         q[0] = (bsiz - 8L);
  80.         q[1] = NULL;
  81.         p[4] = FREE;
  82.         return(p);
  83.         }
  84.     return(NULL);
  85.     }
  86.  
  87. static char *splitblk(addr, size)
  88.     register long **addr;
  89.     register long size;
  90. /*
  91.  *    Split block at *<addr> into a used block containing <size> bytes
  92.  *    and a free block containing the remainder.
  93.  */
  94.     {
  95.     register long n, *p, *q;
  96.  
  97.     n = *(p = *addr);            /* get actual block size */
  98.     if(n > (size + 8L))            /* is it worth splitting? */
  99.         {
  100.         n -= size;
  101.         /* calculate "break" point */
  102.         q = ((long *) (((char *) p) + size));
  103.         p[0] = size;
  104.         q[0] = n;
  105.         q[1] = p[1];
  106.         *addr = q;
  107.         }
  108.     else                    /* not worth splitting */
  109.         *addr = ((long *) p[1]);    /* remove from free list */
  110.     *((char *) p) = USED;            /* mark block "used" */
  111.     return(p);
  112.     }
  113.  
  114. static char *findblk(size)
  115.     register long size;
  116. /*
  117.  *    Find the smallest unused block containing at least <size> bytes.
  118.  */
  119.     {
  120.     register int i;
  121.     register long n, tsiz = 0x7FFFFFFFL, **p, *q, *tptr = NULL;
  122.  
  123.     for(i=0; i<MAXBLK; ++i)
  124.         {
  125.         if((p = ((long **) _mblk[i])) == NULL)
  126.             continue;        /* skip unavailable heaps */
  127.         while(q = *p)
  128.             {
  129.             n = *q;
  130.             if((n >= size) && (n < tsiz))        /* it fits */
  131.                 {
  132.                 tsiz = n;
  133.                 tptr = ((long *) p);
  134.                 }
  135.             p = ((long **) (q + 1));
  136.             }
  137.         }
  138.     return(tptr);
  139.     }
  140.  
  141. /*--------------------- Documented Functions ---------------------------*/
  142.  
  143. char *lalloc(size)
  144.     register long size;
  145.     {
  146.     register char *p;
  147.  
  148.     if (size <= 4L)
  149.         size = 8L;            /* minimum allocation */
  150.     else
  151.         size = (size + 5L) & ~1L;    /* header & alignment */
  152.     if((p = findblk(size)) == NULL)
  153.         if((p = makeblk(size)) == NULL)
  154.             return(NULL);
  155.     p = splitblk(p, size);
  156.     return(p + 4);            /* skip over header */
  157.     }
  158.  
  159. char *malloc(size)
  160.     unsigned int size;
  161.     {
  162.     return(lalloc((long) size));
  163.     }
  164.  
  165. char *calloc(n, size)
  166.     unsigned int n;
  167.     size_t size;
  168.     {
  169.     register long total;
  170.     register char *p, *q;
  171.  
  172.     total = (((long) n) * ((long) size));
  173.     if(p = lalloc(total))
  174.         for(q=p; total--; *q++ = 0)
  175.             ;
  176.     return(p);
  177.     }
  178.